﻿using System;
using System.Collections.Generic;
using STeaL.Functional;
using System.Diagnostics;

namespace STeaL.Algorithm {

  public static partial class IEnumarableExtensions {
#region is_sorted
    public static bool is_sorted<T>(this IEnumerable<T> setX, Func<T,T,bool> pred) {
      IEnumerator<T> X = setX.GetEnumerator();
      if ( X.MoveNext() ) {
        IEnumerator<T> N = setX.GetEnumerator();
        N.MoveNext();
        while ( N.MoveNext() ) {
          if ( pred(N.Current, X.Current) ) {
            return false;
          }
          X.MoveNext();
        }
      }
      return true;
    }

    public static bool is_sorted<T>(this IEnumerable<T> setX) where T: IComparable<T> {
      return is_sorted(setX, rel_op.less<T>);
    }

#endregion
#region includes
    public static bool includes<T>(this IEnumerable<T> setX, IEnumerable<T> setY, Func<T,T,bool> pred ) {
      Debug.Assert( is_sorted(setX, pred) );
      Debug.Assert( is_sorted(setY, pred) );
      IEnumerator<T> X = setX.GetEnumerator();
      IEnumerator<T> Y = setY.GetEnumerator();
      bool hasmoreX = X.MoveNext();
      bool hasmoreY = Y.MoveNext();
      while ( hasmoreX && hasmoreY)  {
        if ( pred(Y.Current, X.Current) ) {
          return false;
        } else if ( pred(X.Current, Y.Current) ) {
          hasmoreX = X.MoveNext();
        } else {
          hasmoreX = X.MoveNext();
          hasmoreY = Y.MoveNext();
        }
      }
      return !hasmoreY;
    }

    public static bool includes<T>(this IEnumerable<T> setX, IEnumerable<T> setY) where T: IComparable<T> {
      return includes(setX, setY, rel_op.less<T>);
    }

#endregion
#region set_union
    public static IEnumerable<T> set_union<T>(this IEnumerable<T> setX, IEnumerable<T> setY, Func<T,T,bool> pred ) {
      IEnumerator<T> X = setX.GetEnumerator();
      IEnumerator<T> Y = setY.GetEnumerator();
      bool hasmoreX = X.MoveNext();
      bool hasmoreY = Y.MoveNext();
      while ( hasmoreX && hasmoreY ) {
        if ( pred(X.Current, Y.Current) ) {
          yield return X.Current;
          hasmoreX = X.MoveNext();
        } else if ( pred(Y.Current, X.Current) ) {
          yield return Y.Current;
          hasmoreY = Y.MoveNext();
        } else {
          yield return X.Current;
          hasmoreX = X.MoveNext();
          hasmoreY = Y.MoveNext();
        }
      }
      while ( hasmoreX ) {
        yield return X.Current;
        hasmoreX = X.MoveNext();
      }
      while ( hasmoreY ) {
        yield return Y.Current;
        hasmoreY = Y.MoveNext();
      }
    }

    public static IEnumerable<T> set_union<T>(this IEnumerable<T> setX, IEnumerable<T> setY) where T : IComparable<T> {
      return set_union(setX, setY, rel_op.less<T>);
    }

#endregion
#region set_intersection
    public static IEnumerable<T> set_intersection<T>(this IEnumerable<T> setX, IEnumerable<T> setY, Func<T,T,bool> pred ) {
      Debug.Assert( is_sorted(setX, pred) );
      Debug.Assert( is_sorted(setY, pred) );
      IEnumerator<T> X = setX.GetEnumerator();
      IEnumerator<T> Y = setY.GetEnumerator();
      bool hasmoreX = X.MoveNext();
      bool hasmoreY = Y.MoveNext();
      while ( hasmoreX && hasmoreY ) {
        if ( pred(X.Current, Y.Current) ) {
          hasmoreX = X.MoveNext();
        } else if ( pred(Y.Current, X.Current) ) {
          hasmoreY = Y.MoveNext();
        } else {
          yield return X.Current;
          hasmoreX = X.MoveNext();
          hasmoreY = Y.MoveNext();
        }
      }
    }

    public static IEnumerable<T> set_intersection<T>(this IEnumerable<T> setX, IEnumerable<T> setY) where T : IComparable<T> {
      return set_intersection(setX, setY, rel_op.less<T>);
    }

#endregion
#region defference
    public static IEnumerable<T> set_difference<T>(this IEnumerable<T> setX, IEnumerable<T> setY, Func<T,T,bool> pred) {
      Debug.Assert( is_sorted(setX, pred) );
      Debug.Assert( is_sorted(setY, pred) );
      IEnumerator<T> X = setX.GetEnumerator();
      IEnumerator<T> Y = setY.GetEnumerator();
      bool hasmoreX = X.MoveNext();
      bool hasmoreY = Y.MoveNext();
      while ( hasmoreX && hasmoreY ) {
        if ( pred(X.Current, Y.Current) ) {
          yield return X.Current;
          hasmoreX = X.MoveNext();
        } else if ( pred(Y.Current, X.Current) ) {
          hasmoreY = Y.MoveNext();
        } else {
          hasmoreX = X.MoveNext();
          hasmoreY = Y.MoveNext();
        }
      }
      while ( hasmoreX ) {
        yield return X.Current;
        hasmoreX = X.MoveNext();
      }
    }

    public static IEnumerable<T> set_difference<T>(this IEnumerable<T> setX, IEnumerable<T> setY) where T : IComparable<T> {
      return set_difference(setX, setY, rel_op.less<T>);
    }

#endregion
#region symmetric difference
    public static IEnumerable<T> set_symmetric_difference<T>(this IEnumerable<T> setX, IEnumerable<T> setY, Func<T,T,bool> pred) {
      Debug.Assert( is_sorted(setX, pred) );
      Debug.Assert( is_sorted(setY, pred) );
      IEnumerator<T> X = setX.GetEnumerator();
      IEnumerator<T> Y = setY.GetEnumerator();
      bool hasmoreX = X.MoveNext();
      bool hasmoreY = Y.MoveNext();
      while ( hasmoreX && hasmoreY ) {
        if ( pred(X.Current, Y.Current) ) {
          yield return X.Current;
          hasmoreX = X.MoveNext();
        } else if ( pred(Y.Current, X.Current) ) {
          yield return Y.Current;
          hasmoreY = Y.MoveNext();
        } else {
          hasmoreX = X.MoveNext();
          hasmoreY = Y.MoveNext();
        }
      }
      while ( hasmoreX ) {
        yield return X.Current;
        hasmoreX = X.MoveNext();
      }
      while ( hasmoreY ) {
        yield return Y.Current;
        hasmoreY = Y.MoveNext();
      }
    }

    public static IEnumerable<T> set_symmetric_difference<T>(this IEnumerable<T> setX, IEnumerable<T> setY) where T : IComparable<T> {
      return set_symmetric_difference(setX, setY, rel_op.less<T>);
    }

#endregion
  }
}
